/* 

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

 

示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]


示例 2：
输入：n = 1
输出：[["Q"]]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-queens
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
    const position = [];
    const res = [];

    const isValid = function (row, col) {
        for (let i = 0; i < row; i++) {
            if (col === position[i]) return false;
            if (Math.abs((row - i) / (col - position[i])) === 1) return false
        }
        return true;
    }

    const generateString = function (arr) {
        const len = arr.length;
        const res = [];

        for (let i = 0; i < len; i++) {
            let str = ""
            for (let j = 0; j < len; j++) {
                if (arr[i] === j) str += "Q";
                else str += ".";
            }
            res.push(str);
        }

        return res;
    }

    const traverse = function (startDepth, endDepth) {
        if (startDepth === endDepth) {
            res.push(generateString(position));
            return;
        }

        for (let col = 0; col < endDepth; col++) {
            if (isValid(startDepth, col)) {
                position[startDepth] = col;
                traverse(startDepth + 1, endDepth);
            }
        }
    }

    traverse(0, n);
    return res;
};